The present invention relates generally to fabrication of integrated circuits and more particularly to a process for reducing failures due to round-off errors during design rule checking algorithms.
Integrated circuits must be layed out so that components (i.e., resistors, transistors, diodes, capacitors, and the like) and wiring between the components do not intersect at undesired locations but do have sufficient spacing between them to operate reliably. To meet these requirements, integrated circuit layout is performed using a computer program applying a design rule checking (DRC) algorithm. DRC can require checking millions or even tens of millions of geometric shapes to verify that they satisfy the closeness requirements (i.e., design rules) for reliable operation of the integrated circuit being designed.
DRC algorithms typically perform Boolean operations such as intersection, union, and difference using polygons to represent the components and wiring on the integrated circuit. In many DRC implementations, the polygons are represented using long or integer coordinates. When Boolean operations such as intersection, union, and difference are performed using these polygons, vertex coordinates are computed by intersecting two edges using floating point computations. Then, these vertex coordinates are rounded to long or integers for the output polygon. As a result of this rounding, the output polygons can intersect spuriously. For example, an output polygon can self-intersect to create a bow-tie, or an inside loop can intersect an outside loop that is supposed to enclose the inside loop. These spurious intersections, create undefined or ill defined point-sets, resulting in ambiguous or wrong answers for DRC operations.
Many DRC algorithms operate on the assumption that the output of the Boolean operations that form the foundation of these algorithms are regular and well-defined point sets, and that these point-sets are defined by well-defined polygonal boundaries. Round-off errors during Boolean computations can cause algorithm failures without warning. These undetected errors can cause severe consequences, including wasted computation time due to ambiguous or wrong results or even defective dies due to undetected errors.
The importance of overcoming the various deficiencies noted above is evidenced by the extensive technological development directed to the subject, as documented by the relevant patent and technical literature. Several approaches disclosed in the technical literature focus on minimizing round-off errors in geometric computations. One approach uses a statistical approach to minimize errors, as described in xe2x80x9cRecipes for Geometry and Numerical Analysisxe2x80x94Part I: An Empirical Study,xe2x80x9d by Dobkin et al., Proceedings of the ACM Symposium on Computational Geometry, page 93 (1988). Another approach provides a method for minimizing the effect of round-off error by using least significant bit calculations, as described in xe2x80x9cNumerical Stability of Simple Geometric Algorithms in the Plane,xe2x80x9d by Ottmann et al., Proceedings of the ACM Symposium on Computational Geometry, page 163 (1993). Yet another approach uses minimum feature size for Boolean intersections, as described in xe2x80x9cConsistent Calculations for Solids Modeling,xe2x80x9d by Segal et al., Proceedings of the ACM Symposium on Computational Geometry, page 29 (1985). These approaches minimize, but do not eliminate, rounding errors. Because rounding errors are not eliminated, they can still cause problems for DRC algorithms.
Other approaches attempt to eliminate spurious intersections caused by round-off error, but are very expensive and difficult to implement due to memory requirements, inefficient computational methods, and quantity of computations. xe2x80x9cEpsilon Geometry: Building Robust Algorithms for Imprecise Computations,xe2x80x9d Guibas et al., Proceedings of the ACM Symposium on Computational Geometry, page 208 (1989), teaches a method using a fuzzy tool for topological consistency checking. xe2x80x9cGeometric and Solid Modeling,xe2x80x9d by C. Hoffmann, pages 111-53 (Morgan Kaufmann Publishers, Inc. 1989), attempts a topological reasoning method for maintaining topological consistency by using non-redundancy. xe2x80x9cEfficient Exact Arithmetic for Computational Geometry,xe2x80x9d Fortune et al., ACM Symposium on Conceptual Geometry, page 163 (1993), advocates computations in the exact precision domain. xe2x80x9cInterval Methods for Processing Geometric Objects,xe2x80x9d Mudur et al., IEEE Computer Graphics and Applications, 4(2):7 (1984), teaches an interval arithmetic approach for computing curve intersections using two bounds for each integer. xe2x80x9cFinite-Resolution Computational Geometry,xe2x80x9d Greene et al., Proceedings of Twenty-Seventh Annual IEEE-FOCS Conference, page 143 (1986), uses an algorithm for line intersection using number theoretic algorithms. Each of these approaches requires at least one of excess data storage, inefficient algebraic systems, and excess computationsxe2x80x94making the approaches prohibitively expensive to implement in a DRC algorithm.
Yet another approach is disclosed in xe2x80x9cVerifiable Implementations of Geometric Algorithms Using Finite Precision Arithmetic,xe2x80x9d V. Milenkovic, in Geometrical Reasoning, pages 377-401 (D. Kapur and J. Mundy eds., MIT Press, 1989). Milenkovic teaches a method for eliminating spurious intersections of two separate polygons by cracking edges at any vertex (vi) whose coordinate location is within an error value (xcex5) of any edge (e1, e2, e3,, and so on). The error value (xcex5) is defined as the maximum possible error, which is a function of the maximum round-off and the number of arithmetic operations (for DRC algorithms, the number of arithmetic operations can be in the millions or even tens of millions). Each edge which is within xcex5 of a vertex of the other polygon is then converted to multiple new edges having endpoints at each of the vertices that were within xcex5 of that edge. Because this edge cracking can create new edge-vertex pairs within the error value (xcex5), the process is repeated until no further edge cracking is possible.
Although this method eliminates certain spurious intersections, it may cause many more edge cracks than are necessary (i.e., the proximity of the edge-vertex pair would not cause spurious intersections, because the vertex would not be rounded off to the opposite side of the edge or the particular edge-vertex proximity would be eliminated by a Boolean operation). Unnecessary edge cracks would cause a DRC program to expend excess memory and computation time. In addition, unnecessary edge cracking can cause unwarranted distortion of the geometric shapes used in a DRC application.
Therefore, an object of the present invention is to provide a process for preventing failures due to round-off during design rule checking algorithms. It is a further object of the present invention to provide a process for preventing failures due to round-off during design rule checking algorithms which requires minimum memory and computational time.
To achieve these and other objects, and in view of its purposes, the present invention provides a process for proximity-based rounding. A vertex which is close to an edge for which it is not an endpoint is embedded on that edge. The edge is then converted to two edges, each having one of the original endpoints and both having the embedded vertex as the other endpoint.
In one embodiment of the present invention, a design rule checking algorithm uses proximity-based rounding after a Boolean operation is performed on input polygons to produce an output polygon. Each vertex of the output polygon is checked for proximity to each edge of the output polygon by determining whether the vertex is located within an integer box through which the edge passes. If so, the vertex is embedded on the edge. Following proximity-based rounding, the coordinates (vertices) of the output polygon are rounded to integers. Because the vertex and the point embedded on the edge in proximity to the vertex are now the same point, they are rounded to the same integer and the edges associated with the vertex do not spuriously intersect with the edge in proximity to the vertex.